#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution
{
private:
  void backtrack(vector<vector<int>> &res, vector<int> &track, int target, int begin, vector<int> candidates)
  {
    if (target < 0)
      return;
    if (target == 0)
      res.push_back(track);

    for (int i = begin; i < candidates.size(); i++)
    {
      // 重点理解这里剪枝，前提是候选数组已经有序
      if (target - candidates[i] < 0)
      {
        break;
      }

      track.push_back(candidates[i]);
      cout << "递归之前=>";
      for (auto c : track)
      {
        cout << c << ",";
      }
      cout << "剩余=" << target - candidates[i];
      cout << endl;

      backtrack(res, track, target - candidates[i], i, candidates); // 理解这里放i,进入递归还是i=0的子树，所以可以用的，但是进入第二层i=1的时候，此时i已经加1了避免了重复使用的情况
      track.pop_back();

      cout << "递归之后=>";
      for (auto c : track)
      {
        cout << c << ",";
      }
      cout << endl;
    }
    return;
  }

public:
  vector<vector<int>> combinationSum(vector<int> candidates, int target)
  {
    int len = candidates.size();
    vector<vector<int>> res;
    vector<int> track;
    if (0 == len)
      return res;

    sort(candidates.begin(), candidates.end());

    backtrack(res, track, target, 0, candidates);

    return res;
  }
};

int main()
{

  Solution solution = Solution();
  vector<int> candidates = {2, 3, 6, 7};
  int target = 7;
  vector<vector<int>> res = solution.combinationSum(candidates, target);
  cout << "输出：";
  for (auto targets : res)
  {
    for (auto target : targets)
    {
      cout << target << ",";
    }
    cout << "]";
  }
  cout << endl;
}